/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/repeated-dna
   @Language: C++
   @Datetime: 19-06-25 10:07
   */

class Solution {
public:
	/**
	 * @param s: a string represent DNA sequences
	 * @return: all the 10-letter-long sequences 
	 */
	vector<string> findRepeatedDna(string &s) {
		// write your code here
		vector<string> vs;
		unordered_set<string> dict;
		for(int i=0; i+10<=s.length(); ++i){
			const string str=s.substr(i,10);
			if(s.find(str,i+1)!=s.npos) dict.insert(str);
		}
		for(const auto &str:dict)
			vs.push_back(str);
		return vs;
	}
};
